package main

import "fmt"

func main()  {
	startWord := "hit"
	endWord := "cog"
	wordList := []string{"hot","dot","dog","lot","log","cog"}

	fmt.Println(findWordMinDeeps(startWord,endWord,wordList))
}

func findWordMinDeeps(startWord,endWord string,wordList []string) uint8 {
	if len(startWord) <= 0 || len(endWord) <= 0 || startWord == endWord || len(startWord) != len(endWord) {
		return 0
	}

	wordListMap := map[string][]string{}
	isExistEndWord := false
	for _,v := range wordList {
		if v == startWord {
			continue
		}
		if v == endWord {
			isExistEndWord = true
		}

		for k1,_:= range v {
			temWord := v[:k1] + "*"
			if k1 < (len(v)){
				temWord += v[k1+1:]
			}
			wordListMap[temWord] = append(wordListMap[temWord],v)
		}
	}

	if !isExistEndWord {
		return 0
	}

	queue := []string{startWord}
	var visited  map[string]bool
	visited = map[string]bool{}
	var deep uint8 = 1
	for len(queue) > 0 {
		size := len(queue)
		for _,v:= range queue{
			if visited[v]{
				continue
			}
			if v == endWord {
				return deep
			}
			visited[v] = true
			
			for k1,_ := range v{
				temWord := v[:k1] + "*"
				if k1 < len(v) {
					temWord += v[k1+1:]
				}
				if _,ok := wordListMap[temWord];ok {
					queue = append(queue,wordListMap[temWord]...)
				}
			}
		}
		queue = queue[size:]
		deep++
	}

return 0
}
